#include "stdafx.h"
#include "KMP.h"
#include <string>
int KMP_StringMatch(char * main, int mLen, char * pattern, int pLen, int pos){
	int * next = new int[pLen+1];
	GetNextArray(pattern, pLen, next);
	int i = pos, j = 0;
	for(;;){
		if(i >= mLen || j >= pLen) break;
		if(j ==-1 ||main[i] == pattern[j]){ //condition compare with original ver.
			++i; ++j;
		}else{
			j = next[j];//cwov
		}
	}
	delete [] next;
	if(j == pLen) return i- pLen;
	else return -1;
}

//known condition :p0p1...p(k-1) = p(j-k+1)p(j-k+2)...p(j-1)
//for one possible :p(k)  = p(j), next[j] = k + 1
//anothor: p(k) != p(j), 
void GetNextArray(char* pattern, int pLen, int next[]){
	int k = -1, j = 0;
	next[0] = -1;
	for(;;){
		if(j >= pLen) break;
		if(k == -1 || pattern[k] == pattern[j]){
			++k; ++j;
			next[j] = k;
		}else{
			k = next[k];
		}
	}
}

//original version
int StringMatch(char * main, int mLen ,char * pat, int pLen, int pos = 0){
	int i = pos, j = 0;
	for(;;){
		if(i >= mLen || j >= pLen) break;
		if(main[i] == pat[j]){
			++i; ++j;
		} else{
			i = i - j + 2;
			j = 0;
		}
	}
	if(j == pLen) return i-j;
	else return -1;
}